package leetcode.lcp0041;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.H;

public class Solution {
	int ans;

	int[] direction = new int[] { -1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1 };

	int m, n;

	public int flipChess(String[] chessboard) {
		m = chessboard.length;
		char[][] board = new char[m][];
		for (int i = 0; i < chessboard.length; i++) {
			board[i] = chessboard[i].toCharArray();
		}
		ans = 0;
		H.print(board);
		n = board[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				char c = board[i][j];
				if (c == '.') {
					char[][] copy = new char[m][n];
					for (int k = 0; k < chessboard.length; k++) {
						copy[k] = chessboard[k].toCharArray();
					}
					copy[i][j] = 'X';
					int cur = infect(copy, index(i, j));
					if (cur > ans) {
						ans = cur;
					}
				}
			}
		}
		return ans;
	}

	public int index(int i, int j) {
		return i * n + j;
	}

	private int infect(char[][] board, int index) {
		int x = index / n, y = index % n;
		int cur = 0, sum = 0;
		List<Integer> list = new ArrayList<>();
		for (int k = 0; k < direction.length; k += 2) {
			int x2 = x + direction[k];
			int y2 = y + direction[k + 1];
			List<Integer> l = new ArrayList<>();
			l = f(board, x2, y2, direction[k], direction[k + 1], l);
			if (l != null && l.size() != 0) {
				for (int c : l) {
					board[c / n][c % n] = 'X';
				}
				sum += l.size();
				list.addAll(l);
			}
		}
		for (int c : list) {
			sum += infect(board, c);
		}
		return sum;
	}

	private List<Integer> f(char[][] board, int x, int y, int x2, int y2, List<Integer> l) {
		if (x < 0 || x == m || y < 0 || y == n) {
			return null;
		}
		if (board[x][y] == '.') {
			return null;
		}
		if (board[x][y] == 'X') {
			return l;
		}
		l.add(index(x, y));
		return f(board, x + x2, y + y2, x2, y2, l);
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		int ans = so.flipChess(H.str2array2("[\"X....\",\".O...\",\".OO..\",\".OOO.\",\".O...\",\".X...\"]"));
//		System.out.println(ans);
		int ans1 = so.flipChess(H.str2array2("[\".XXOXX\",\"XOOOOO\",\"......\"]"));
//["X....",".O...",".OO..",".O.O.",".O...",".X...."]
//["X....",".O...","..O..","...O.",".....",".X...."]
//[".XXOXX","XOOOOO","......"]
//["XOX","OOO",".OO"]
//["....X.","....X.","XOOO..","......","......"]
//[".X.",".O.","XO."]
//[".......",".......",".......","X......",".O.....","..O....","....OOX"]
	}
}
